package demo.practice.dfs;


import java.util.*;

/**
 * 本题难点
 * <p>
 * 1.构造树
 * 2.dfs构造路径并  回溯
 * 3.数字二进制  构造trie
 * -> dfs遍历后拿到的数字  添加到 trie
 * -> trie求当前节点路径下  与queries 相应节点的最大XOR
 * -> 回溯前删除trie中的当前节点
 */
public class P1938 {



    class Trie {
        Map<Integer, Trie> child = new HashMap<>();
        int child_count = 0;

        public void insert(int num) {
            Trie cur = this;
            for (int i = 30; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if (cur.child.get(bit) == null) {
                    cur.child.put(bit, new Trie());
                    cur = cur.child.get(bit);
                    cur.child_count++;  //当前分支有几个子节点
                } else {
                    cur = cur.child.get(bit);
                    cur.child_count++;  //当前分支有几个子节点
                }
            }
        }

        public void remove(int num) {
            Trie cur = this;
            for (int i = 30; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if (cur.child.get(bit) == null) {
                    return;
                } else {
                    cur.child.get(bit).child_count--;
                    if (cur.child.get(bit).child_count == 0) {
                        cur.child.remove(bit);
                        return;
                    } else {
                        cur = cur.child.get(bit);
                    }
                }
            }
        }

        public int maxXOR(int query) {
            Trie cur = this;
            int res = 0;
            for (int i = 30; i >= 0; i--) {
                int bit = (query >> i) & 1;

                if (bit == 0) {
                    if (cur.child.get(1) != null) {
                        //这一位有值
                        res = res | (1 << i);
                        cur = cur.child.get(1);
                    } else {
                        cur = cur.child.get(0);
                    }
                } else {
                    if (cur.child.get(0) != null) {
                        //这一位有值
                        res = res | (1 << i);
                        cur = cur.child.get(0);
                    } else {
                        cur = cur.child.get(1);
                    }
                }
            }
            return res;
        }
    }


    public static void main(String[] args) {
        P1938 p1938 = new P1938();
        int[] ints = p1938.maxGeneticDifference(new int[]{-1,0,0,0,3}, new int[][]{{4, 6}, {0, 0}, {0, 3},{1,8},{4,0}});
        System.out.println(Arrays.toString(ints));
    }

    public int[] maxGeneticDifference(int[] parents, int[][] queries) {
        if (parents == null || parents.length == 0 || queries == null || queries.length == 0) {
            return new int[0];
        }

        //k= 父节点的基因号（也是原数组的索引）  v为该节点的子节点（标准的有两个孩子，这里因为部分左右，直接用一个list存储）的基因号（也是原数组的索引）
        Map<Integer, List<Integer>> tree = new HashMap<>();

        int root = -1;
        for (int i = 0; i < parents.length; i++) {
            if (!tree.containsKey(parents[i])) {    //parents[i] 是当前元素的父节点
                tree.put(parents[i], new ArrayList<>());
            }
            tree.get(parents[i]).add(i);
            if (parents[i] == -1)//获得根节点的基因号（原数组的索引）
                root = i;
        }
        Map<Integer, ArrayList<int[]>> queryEls = new HashMap<>();//所有需要查询的节点，及做XOR 的值
        for (int i = 0; i < queries.length; i++) {

            if (!queryEls.containsKey(queries[i][0])) {
                queryEls.put(queries[i][0], new ArrayList<int[]>());
            }
            queryEls.get(queries[i][0]).add(new int[]{queries[i][1], i});
            //queryEls.put(queries[i][0], new int[]{queries[i][1], i});
        }


        int[] res = new int[queries.length];
        Trie t = new Trie();
        dfs(tree, root, queryEls, res, t);
        return res;
    }


    private void dfs(Map<Integer, List<Integer>> tree, int root, Map<Integer, ArrayList<int[]>> queryEls, int[] res, Trie t) {
        //在trie中添加元素
        t.insert(root);
        if (queryEls.containsKey(root)) {
            for (int[] qr : queryEls.get(root)) {
                res[qr[1]] = t.maxXOR(qr[0]);
                System.out.println(qr[0]);
            }

        }
        //深度优先遍历
        if (tree.containsKey(root)) {
            List<Integer> child = tree.get(root);
            for (Integer c : child) {
                dfs(tree, c, queryEls, res, t);
            }
        }
        t.remove(root);
        //在trie中移除深度到的节点
    }


}
